Jump to content

Talk:Pointer machine

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

Kolmogorov-Uspensky Machines

[edit]

This section definitely needs more detail. To say "it's like a SMM, but not" won't do. Now, it's my understanding that KU machines are actually described better and more succinctly by people other than Kolmogorov, but perhaps he should be given a say too.

Finding the English translation of the original paper behind a paywall, I attempted to run the Russian paper through Google's OCR and translator. The translation I did get was comprehensible but less than ideal, and the OCR gave up halfway through. Surely a Russian mathematics student could summarize?

From what I've read elsewhere, Kolmogorov explained his system in terms of replacing a bounded portion of the graph with another graph, with no instantaneous effects outside the neighborhood and with all information stored in the graph itself. This seems rather different from the Harvard architecture implied by comparing it to the SMM. How does one reconcile the different descriptions?

I'd particularly like to see more detail about the instruction set. Because of the limitation on inbound links and the requirement for symmetric links, one needs to be more specific than with the SMM instructions:

  • Suppose one is moving a link and the removed link was the only inbound link that a node had to the rest of the graph. Does doing so cause this node to become completely disconnected? Or is the instruction simply aborted because of its impossibility?
  • Or suppose one is moving a link to a node that already has the maximum number of inbound links. The in-degree in a KU graph is limited. Does the move instruction fail? It can't always delete a link without touching off a series of failures of the symmetry rule, thus violating the bounded neighborhood rule.

I'm also left wondering whether one can refer to nodes by a unique name or whether one must do so. And since KU machines have an instruction to choose a new active node, how does that work?

Finally, I find it rather ironic that I can't find a reference implementation in a modern computer language, some half a century later. Isn't the point of a mathematical definition to bring clarity to your discussions with both mathematicians and non-mathematicians?

99.118.9.187 (talk) 03:36, 6 April 2014 (UTC)[reply]


Wikification

[edit]

I just added the Wikify template because of some reasons:

  • Wikilinks needed in some sections.
  • References should probably use <ref> instead, especially the inline ones.

Also, the section about SMM goes pretty in-depth with describing what "language", "string" and so on means in this context, something that I think is described in their respective wikipedia article, and I don't know if that much information is needed in this article (?). ~FireyFly tc 17:49, 6 July 2010 (UTC)[reply]